package 牛客算法篇;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-03-04
 * Time:19:22
 */

import java.util.LinkedList;
import java.util.Queue;

/**
 *
 牛客算法篇:BM35 判断是不是完全二叉树
 广度优先搜索(BFS)
 描述
 给定一个二叉树，确定他是否是一个完全二叉树。
 完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。（第 h 层可能包含 [1~2h] 个节点）
 数据范围：节点数满足 1≤n≤100 1≤n≤100
 示例1
 输入：
 {1,2,3,4,5,6}
 返回值：
 true
 */
public class isCompleteTree {
    public static void main(String[] args) {
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode e = new TreeNode(4);
        TreeNode f = new TreeNode(5);
        TreeNode g = new TreeNode(6);
        TreeNode h = new TreeNode(7);

        a.left = b;
        a.right = c;
        b.left = e;
        b.right = f;
        c.left = g;
        c.right = null;
        isCompleteTree(a);
    }
    public static boolean isCompleteTree (TreeNode root) {
        // write code here
        // write code here
        if (root == null) return true;

        boolean hasNull = false;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                hasNull = true;
                continue;
            }
            if (hasNull) return false;
            queue.offer(node.left);
            queue.offer(node.right);
        }
        return true;
    }
}
